package 单周赛.september;

import java.util.Arrays;
import java.util.List;

/**
 *
 */
public class 第363场单周赛 {

    public static void main(String[] args) {

        第363场单周赛 impl = new 第363场单周赛();

        System.out.println(impl.countWays(Arrays.asList(6, 0, 3, 3, 6, 7, 2, 7)));

        System.out.println(Math.pow(2, 31));

    }

    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
        int sum = 0;

        for (int i = 0; i < nums.size(); i++) {
            if (Integer.bitCount(i) == k) {
                sum += nums.get(i);
            }
        }

        return sum;
    }

    /**
     * 排序+贪心
     * 1，选将学生排序，然后枚举要选的学生个数 k
     * 2，这位学生被选中，并且被选中的学生人数 严格大于 nums[i]，那么 nums[i] 越小越容易
     * 符合条件，由于 nums 是从小到大排序的，那么直接选择前 [0,k-1] 的学生，判断其中选中
     * 人数k > 最大值 num[k-1]
     * 3，被选中的学生人数 严格小于 nums[i]，选择后 [k,n-1] 的学生，判断其中选中
     * 人数k > 最小值 num[k]
     */
    public int countWays(List<Integer> nums) {
        int ans = 0;
        nums.sort((a, b) -> a - b);

        if (0 < nums.get(0)) {
            ans++;
        }
        for (int student = 1; student <= nums.size(); student++) {
            if (student > nums.get(student - 1) && (student == nums.size() || student < nums.get(student))) {
                ans++;
            }
        }

        return ans;
    }


    /**
     * 二分查找
     * 注意：
     * 1，预算 budget = 0 时，制造的合计数不一定为 0 ，因为有提前储存的金属 stock
     * 1，统计当前预算的时候，使用 long 统计，并判断 > budget 时退出统计，避免数字溢出
     */
    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        int ans = 0;

        for (List<Integer> composit : composition) {

            int curAlloys = binarySearch(composit, stock, cost, budget);

            ans = Math.max(ans, curAlloys);
        }

        return ans;
    }

    private int binarySearch(List<Integer> composit, List<Integer> stock, List<Integer> cost, int budget) {
        int ans = 0;
        int left = 0, right = 10_000_000_00;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            long curBudget = 0;
            for (int i = 0; i < composit.size(); i++) {
                curBudget += Math.max(0, 1L * composit.get(i) * mid - stock.get(i)) * cost.get(i);
                if (curBudget > budget) {
                    break;
                }
            }
            if (curBudget <= budget) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }

}
